/*  MicroJava Parser (HM 06-12-28)
    ================
*/
package MJ;

import java.util.*;

import MJ.SymTab.*;
//import MJ.CodeGen.*;

public class Parser {
	private static final int  // token codes
		none      = 0,
		ident     = 1,
		number    = 2,
		charCon   = 3,
		plus      = 4,
		minus     = 5,
		times     = 6,
		slash     = 7,
		rem       = 8,
		eql       = 9,
		neq       = 10,
		lss       = 11,
		leq       = 12,
		gtr       = 13,
		geq       = 14,
		assign    = 15,
		semicolon = 16,
		comma     = 17,
		period    = 18,
		lpar      = 19,
		rpar      = 20,
		lbrack    = 21,
		rbrack    = 22,
		lbrace    = 23,
		rbrace    = 24,
		class_    = 25,
		else_     = 26,
		final_    = 27,
		if_       = 28,
		new_      = 29,
		print_    = 30,
		program_  = 31,
		read_     = 32,
		return_   = 33,
		void_     = 34,
		while_    = 35,
		eof       = 36;
	private static final String[] name = { // token names for error messages
		"none", "identifier", "number", "char constant", "+", "-", "*", "/", "%",
		"==", "!=", "<", "<=", ">", ">=", "=", ";", ",", ".", "(", ")",
		"[", "]", "{", "}", "class", "else", "final", "if", "new", "print",
		"program", "read", "return", "void", "while", "eof"
		};

	private static Token t;			// current token (recently recognized)
	private static Token la;		// lookahead token
	private static int sym;			// always contains la.kind
	public  static int errors;  // error counter
	private static int errDist;	// no. of correctly recognized tokens since last error

	private static Obj currentMethod;
	
	private static BitSet exprStart, statStart, statFollow, declStart, declFollow, factStart;

	//------------------- auxiliary methods ----------------------
	private static void scan() {
		t = la;
		la = Scanner.next();
		sym = la.kind;
		errDist++;

		/*
		System.out.print("line " + la.line + ", col " + la.col + ": " + name[sym]);
		if (sym == ident) System.out.print(" (" + la.string + ")");
		if (sym == number || sym == charCon) System.out.print(" (" + la.val + ")");
		System.out.println();*/
	}

	private static void check(int expected) {
		if (sym == expected) scan();
		else error(name[expected] + " expected");
	}

	public static void error(String msg) { // syntactic error at token la
		if (errDist >= 3) {
			System.out.println("-- line " + la.line + " col " + la.col + ": " + msg);
			errors++;
		}
		errDist = 0;
	}

	//-------------- parsing methods (in alphabetical order) -----------------

	// Program = "program" ident {ConstDecl | ClassDecl | VarDecl} '{' {MethodDecl} '}'.
	private static void Program() {
		check(program_);
		Tab.openScope();
		check(ident);
		boolean end = false;
		while(!end){
			switch(sym){
				case final_: ConstDecl(); break;
				case ident: VarDecl(); break;
				case class_: ClassDecl(); break;
				default: end = true; break;
			}
		}
		check(lbrace);
		while(sym == ident || sym == void_){MethodDecl();}
		check(rbrace);
		// check if the main() method exists
		// if there is no main method, main is undeclared error will be triggered
		Obj o = Tab.find("main"); 
		if(o==null || o.kind!=Obj.Meth || o.nPars !=0){
			error("main() method has parameters");
		}
		Tab.closeScope();

	}
	
	// ConstDecl = "final" Type ident "=" (number | charConst) ";".
	private static void ConstDecl() {
		check(final_);
		Struct type = Type();
		check(ident);
		String name = t.string;
		check(assign);
		if(sym == number){ 
			if(type == Tab.intType) error("char constant expected");  scan();
		} else  
		if(sym == charCon){
			if(type == Tab.charType) error("int constant expected"); scan();
		} else error("Wrong assignment");
		check(semicolon);
		// insert constant to the symbol table
		Tab.insert(Obj.Con, name, type);
	}
	
	//VarDecl = Type  ident {"," ident } ";".
	private static void VarDecl() {
		Struct type = Type();
		for(;;){		
			check(ident);
			String name = t.string;	
			Tab.insert(Obj.Var, name, type);
			if(sym == comma)scan(); else break;
		}
		check(semicolon);
	}
	
	//ClassDecl = "class" ident "{" {VarDecl} "}".
	private static void ClassDecl() {
		check(class_);
		check(ident);
		String className = t.string;
		// adding class to the name table
		Struct classStruct = new Struct(Struct.Class);
		Struct classArrStruct = new Struct(Struct.Arr);	
		classArrStruct.elemType = classStruct;
		Obj classObj = Tab.insert(Obj.Type, className, classStruct);
		Tab.insert(Obj.Type, className+"[]", classArrStruct);
		// new scope is opened after the method name
		Tab.openScope();
		check(lbrace);
		while(sym == ident){ VarDecl(); }
		check(rbrace);
		classObj.type.fields = Tab.topScope.locals;
		// class scope is closed after the closing brace
		Tab.closeScope();
	}
	
	//MethodDecl = (Type | "void") ident "(" [FormPars] ")" {VarDecl} Block.
	private static void MethodDecl() {
		Struct retType = null;
		if(sym == ident){ retType = Type(); }
		else 
			if(sym == void_){ retType = Tab.noType; scan(); }
			else error("Invalid method declaration");
		check(ident);
		String methodName = t.string;
		// method is added to the symbol table
		Obj method = Tab.insert(Obj.Meth, methodName, retType);
		// new scope is opened after the method name
		Tab.openScope();
		Parser.currentMethod = method;
		check(lpar);
		if(sym == ident) FormPars();
		check(rpar);
		while(sym == ident){ VarDecl(); }
		Block(retType != Tab.noType); // if retType == null, the method is of type void
		// method scope is closed after the closing brace
		currentMethod.locals = Tab.topScope.locals;
		Tab.closeScope();
		Parser.currentMethod = null;
	}
	
	//FormPars = Type ident  {"," Type ident }.
	private static void FormPars() {
		for(;;){
			Struct type = Type(); 
			check(ident); String name = t.string;
			Tab.insert(Obj.Var, name, type);
			Parser.currentMethod.nPars++;
			if(sym == comma) scan(); else break;
		}
	}
	
	//Type = ident ["[" "]"].
	private static Struct Type() {
		check(ident);
		String typeName = t.string;	
		Obj found = null;
		boolean isArray = false;
		if(sym == lbrack){ scan(); check(rbrack); isArray = true;}
		if(isArray)
			found = Tab.find(typeName+"[]");
		else
			 found = Tab.find(typeName);
		if(found != null && found.kind == Obj.Type )
			return found.type;
		error(typeName + " is not a valid type");
		return Tab.noType;
	}
	
	
	
	//Block = "{" {Statement} "}".
	private static void Block(boolean lookForReturn) {
		boolean returnFound = false;
		check(lbrace);
		for(;;){
			if(lookForReturn && sym == return_) returnFound = true; 
			if(statStart.get(sym) || sym == ident) Statement(); 
			else if(sym == rbrace || sym == eof) break;
			else { 
				error("Invalid start of Statement");
				do scan(); 
				while(!statStart.get(sym) && sym != rbrace && sym != eof && sym != semicolon);
				if(sym == semicolon) scan();
				errDist = 0;
			}
		}
		check(rbrace);
		//TODO solved only partially!!
		if(lookForReturn && ! returnFound) error("Method must return a value");
	}
	
	//Statement = Designator ("=" Expr | "(" [ActPars] ")") ";"
	//			| "if" "(" Condition ")" Statement ["else" Statement]
	//			| "while" "(" Condition ")" Statement
	//			| "return" [Expr] ";"
	//			| "read" "(" Designator ")" ";"
	//			| "print" "(" Expr ["," number] ")" ";"
	//			| Block
	//			| ";".
	private static void Statement() {
		if(sym == ident){
			String identName = la.string;
			NodeAttr typeNA = Designator();
			if(sym == assign){
				scan();
				NodeAttr expNA = Expr();
				if(!typeNA.type.assignableTo(expNA.type)){
					error("Expr cannot be assigned");
				}
					
			}
			else if(sym == lpar){
				check(lpar);
				if(exprStart.get(sym)){ ActPars(identName); }
				check(rpar);
				
			}
			else error("Invalid statement");
			check(semicolon);
		}
		else 
		if(sym == if_){ scan(); check(lpar); Condition(); check(rpar); Statement(); 
			if(sym == else_){ scan(); Statement(); }}
		else
		if(sym == while_){ scan(); check(lpar); Condition(); check(rpar); Statement(); }
		else
		if(sym == return_){ scan();

			if(exprStart.get(sym)){ 
				NodeAttr eNA = Expr();
				if( Parser.currentMethod!=null && 
					Parser.currentMethod.type == Tab.noType)
					error("void method cannot return a value");
				else
				if( Parser.currentMethod!=null &&
					!eNA.type.assignableTo(Parser.currentMethod.type)) 
					error("Invalid type returned");
			}
			else if(Parser.currentMethod!=null && Parser.currentMethod.type!=Tab.noType)
				error("Return value missing");
			
			check(semicolon);
		}
		else
		if(sym == read_){ 
			scan(); check(lpar); NodeAttr dNA = Designator(); check(rpar); check(semicolon); 
			if(dNA.type != Tab.intType && dNA.type != Tab.charType){
				error("Read error");
			}
		}
		else
		if(sym == print_) { 
			scan(); check(lpar); NodeAttr eNA = Expr(); 
			if(sym == comma){ scan(); check(number); }
			check(rpar); check(semicolon);
			if(eNA.type != Tab.intType && eNA.type != Tab.charType){
				error("Print error");
			}
		}
		else
		if(sym == lbrace){ Block(false); }
		else
		if(sym == semicolon){ scan(); }
		else error("Invalid statement");
	}
	
	//ActPars = Expr {"," Expr}.
	private static void ActPars(String methodName) {
		Obj method = Tab.find(methodName);
		if(method.kind != Obj.Meth) error(methodName + " is not a method");
		Obj param = method.locals;
		int i =0;
		for(;;){		
			i++;
			NodeAttr eNA = Expr();
			if(!eNA.type.assignableTo(param.type)) error("Invalid type of parameter " + i);
			if(sym == comma) scan(); else break;
			if(param.next!=null) param = param.next; else break;
		}
		if(i!=method.nPars) error("Wrong number of parameters in the method " + methodName);
		
	}
	
	//Condition = Expr Relop Expr.
	private static void Condition() {
		NodeAttr e1NA = Expr();
		boolean canCompareComplex = (sym == eql || sym == neq);
		Relop(); NodeAttr e2NA = Expr();
		if(!e1NA.type.compatibleWith(e2NA.type))
			error("Relargs not compatible");
		if(((e1NA.type != Tab.intType && e1NA.type != Tab.charType) ||
		   (e2NA.type != Tab.intType && e2NA.type != Tab.charType)) && !canCompareComplex){
			error("Invalid relop on a complex type");
		}
	}
	
	//Relop = "==" | "!=" | ">" | ">=" | "<" | "<=".
	private static void Relop() {
		switch(sym){
			case eql: case neq: case gtr: case geq: case lss: case leq: scan(); break;
			default: error("Invalid relop"); break;
		}
	}
	
	//Expr = ["-"] Term {Addop Term}.
	private static NodeAttr Expr() {
		// TODO MINUS!!!
		boolean minusPresent = false;
		if(sym == minus){ scan(); minusPresent = true; }
		NodeAttr t1NA = Term();
		NodeAttr t2NA = null;
		boolean end = false; 
		boolean addTypesCorrect = true;
		boolean simpleProduction = !(sym == plus || sym == minus);
		while(!end){
			switch(sym){
				case plus: case minus: 
					Addop(); t2NA = Term();  
					if(t2NA.type!=Tab.intType) addTypesCorrect = false;
					break;
				default: end = true; break;
			}
		}
		if(simpleProduction) return t1NA;
		if(t1NA.type != Tab.intType || !addTypesCorrect){
			error("addop error: integers expected");
			return new NodeAttr(Tab.noType);
		}
		return new NodeAttr(Tab.intType);
	}
	
	//Term = Factor {Mulop Factor}.
	private static NodeAttr Term() {
		boolean simpleProduction = true;
		NodeAttr f1NA = Factor();
		NodeAttr f2NA = null;
		boolean end = false;
		boolean mulTypesCorrect = true;
		if(sym == times || sym == slash || sym == rem) simpleProduction = false;
		while(!end){ 
			switch(sym){
				case times: case slash: case rem: 
					Mulop(); f2NA = Factor(); 
					if(f2NA.type!=Tab.intType) mulTypesCorrect = false;
					break;
				default: end = true; break;
			}
		}
		if(simpleProduction){return f1NA;}
		if(f1NA.type != Tab.intType || !mulTypesCorrect){
			error("mulop error: integers expected");
			return new NodeAttr(Tab.noType);
		}
		return new NodeAttr(Tab.intType);
	}
	
	//Factor = Designator ["(" [ActPars] ")"]
	//                    | number
	//                 	  | charConst
	//                 	  | "new" ident ["[" Expr "]"]
	//                 	  | "(" Expr ")".
	private static NodeAttr Factor() {
		switch(sym){
			case ident: 
				String desName = la.string;
				NodeAttr dNA = Designator();
				if(sym == lpar){ scan();
					if(exprStart.get(sym)) ActPars(desName);
				check(rpar); } 
			return new NodeAttr(dNA.type);
			case number: scan(); return new NodeAttr(Tab.intType);
			case charCon: scan(); return new NodeAttr(Tab.charType);
			case new_: scan(); check(ident); String identName = t.string;
				Obj identObj = Tab.find(identName);
				if(sym == lbrack){ 
					scan(); NodeAttr eNA = Expr(); check(rbrack);
					if(eNA.type != Tab.intType) error("Integer expected");
				}
				else{
					if(identObj.type.kind != Struct.Class)
						error("Class expected");
				}
				if(identObj == null) {
					error(identName + " not found"); 
					return new NodeAttr(Tab.noType);
				}
				else return new NodeAttr(identObj.type);
			case lpar: scan(); NodeAttr expNA = Expr(); check(rpar); return new NodeAttr(expNA.type);
			default: error("Invalid factor"); return new NodeAttr(Tab.noType);
		}
	}
	
 	//Designator = ident {"." ident | "[" Expr "]"}.
	private static NodeAttr Designator() {
		boolean end = false;
		Obj actObj = null;
		Obj prevObj = null;
		String actName = "";
		String prevName = "";
		check(ident);
		actName = t.string;
		actObj = Tab.find(actName);
		boolean bracesBefore = false;
		while(!end){
			prevObj = actObj; prevName = actName;
			switch(sym){
				case period: 
					scan(); check(ident); 	
					actName = t.string;
					if(prevObj.type.kind == Struct.Class)
						actObj = Tab.findField(actName, prevObj.type);
					else if(prevObj.type.kind == Struct.Arr 
							&& prevObj.type.elemType.kind == Struct.Class
							&& bracesBefore)
						actObj = Tab.findField(actName, prevObj.type.elemType);
					
					if(prevObj.type.kind == Struct.Arr)
						if(prevObj.type.elemType.kind != Struct.Class )
							error(prevName + " is not a class array");
						else if(!bracesBefore)
							error(prevName + ": braces missing");							
					if(prevObj.type.kind != Struct.Class && prevObj.type.kind != Struct.Arr )
						error(prevName + " is not a class");
					bracesBefore = false;
					break;
				case lbrack: 
					bracesBefore = true;
					if(prevObj.type.kind != Struct.Arr) error(prevName + " is not an array");
					scan(); NodeAttr eNA = Expr(); check(rbrack); 
					if(!(eNA.type == Tab.intType))error("Integer index expected"); break;
				default: end = true; break;
			}
		}
		if(actObj.type.kind == Struct.Arr)
			return new NodeAttr(actObj.type.elemType);
		return new NodeAttr(actObj.type);
	}
	
 	//Addop = "+" | "-".
	private static void Addop() {
		if(sym == plus || sym == minus) scan();
		else error("Invalid addop");
	}
	
 	//Mulop = "*" | "/" | "%".
	private static void Mulop() {
		switch(sym){
			case times: case slash: case rem: scan(); break;
			default: error("Invalid mulop");
		}
	}

	public static void parse() {
		Tab.init();
		// initialize symbol sets
		BitSet s;
		s = new BitSet(64); exprStart = s;
		s.set(ident); s.set(number); s.set(charCon); s.set(new_); s.set(lpar); s.set(minus);

		s = new BitSet(64); statStart = s;
		s.set(ident); s.set(if_); s.set(while_); s.set(read_);
		s.set(return_); s.set(print_); s.set(lbrace); s.set(semicolon);

		s = new BitSet(64); statFollow = s;
		s.set(else_); s.set(rbrace); s.set(eof);

		s = new BitSet(64); declStart = s;
		s.set(final_); s.set(ident); s.set(class_);

		s = new BitSet(64); declFollow = s;
		s.set(lbrace); s.set(void_); s.set(eof);

		// start parsing
		errors = 0; errDist = 3;
		scan();
		Program();
		if (sym != eof) error("end of file found before end of program");
	}

}








